﻿//--------------------------------------------------------------------------
// 
//  Copyright (c) Microsoft Corporation.  All rights reserved. 
// 
//  File: Sorting.cs
//
//--------------------------------------------------------------------------

using System;
using System.Threading;

namespace PFXDemo.Library
{
    public class PFXSorting
    {
        private int[] data;
        private int[] seqdata;
        private int[] parnormdata;
        private int[] paroptdata;
        public PFXSorting()
        {
            var rnd = new Random();
            data = new int[1024*1024];  //Make it beeeeg...
            for (int i = 0; i < data.Length; i++) data[i] = rnd.Next(Int32.MinValue, Int32.MaxValue);   //Fill it in...

            //make 3 copies for the various sorting operations
            seqdata = (int[])data.Clone();
            parnormdata = (int[])data.Clone();
            paroptdata = (int[])data.Clone();
        }

        public void QuickSortSequential()
        {
            QuicksortSequential<int>(seqdata);
        }
        public void QuicksortParallelNormal()
        {
            QuicksortParallelNormal<int>(seqdata);
        }
        public void QuicksortParallelOptimised()
        {
            QuicksortParallelOptimised<int>(seqdata);
        }

        // Sequential quicksort
        private void QuicksortSequential<T>(T [] arr) where T : IComparable<T>
        {
            QuicksortSequential(arr, 0, arr.Length - 1);
        }

        // Parallel quicksort (not optimised)
        private void QuicksortParallelNormal<T>(T[] arr) where T : IComparable<T>
        {
            QuicksortParallelNormal(arr, 0, arr.Length - 1);
        }

        private void QuicksortParallelOptimised<T>(T[] arr) where T : IComparable<T>
        {
            QuicksortParallelOptimised(arr, 0, arr.Length - 1);
        }

        private void QuicksortSequential<T>(T[] arr, int left, int right) where T : IComparable<T>
        {
            if (right > left)
            {
                int pivot = Partition(arr, left, right);
                QuicksortSequential(arr, left, pivot - 1);
                QuicksortSequential(arr, pivot + 1, right);
            }
        }

        private  void QuicksortParallelOptimised<T>(T[] arr, int left, int right) where T : IComparable<T>
        {
            const int SEQUENTIAL_THRESHOLD = 2048;
            if (right > left)
            {
                if (right - left < SEQUENTIAL_THRESHOLD)
                {

                    QuicksortSequential(arr, left, right);
                }
                else
                {
                    int pivot = Partition(arr, left, right);
                    Parallel.Do(
                        () => QuicksortParallelOptimised(arr, left, pivot - 1),
                        () => QuicksortParallelOptimised(arr, pivot + 1, right));
                }
            }
        }

        private void QuicksortParallelNormal<T>(T[] arr, int left, int right) where T : IComparable<T>
        {
            if (right > left)
            {

                    int pivot = Partition(arr, left, right);
                    Parallel.Do(
                        () => QuicksortParallelNormal(arr, left, pivot - 1),
                        () => QuicksortParallelNormal(arr, pivot + 1, right));
            }
        }

        private  void Swap<T>(T[] arr, int i, int j)
        {
            T tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        private  int Partition<T>(T[] arr, int low, int high) where T : IComparable<T>
        {
            // Simply partitioning implementation

            int pivotPos = (high + low) / 2;
            T pivot = arr[pivotPos];
            Swap(arr, low, pivotPos);

            int left = low;
            for (int i = low + 1; i <= high; i++)
            {
                if (arr[i].CompareTo(pivot) < 0)
                {
                    left++;
                    Swap(arr, i, left);
                }
            }

            Swap(arr, low, left);
            return left;
        }
    }
}